"""
最大子数组和问题实现
使用Kadane算法，时间复杂度O(n)
"""

def max_subarray_sum(arr):
    """
    找出整数数组中子数组之和的最大值
    
    Args:
        arr: 整数数组
    
    Returns:
        int: 最大子数组和
    """
    if not arr:
        return 0
    
    # 初始化当前子数组和和最大子数组和
    max_so_far = arr[0]
    max_ending_here = arr[0]
    
    # 遍历数组，从第二个元素开始
    for i in range(1, len(arr)):
        # 决定是扩展当前子数组还是开始新的子数组
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        # 更新全局最大值
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

def find_max_subarray(arr):
    """
    找出最大子数组的起始和结束位置
    
    Args:
        arr: 整数数组
    
    Returns:
        tuple: (最大和, 起始索引, 结束索引)
    """
    if not arr:
        return 0, -1, -1
    
    max_so_far = arr[0]
    max_ending_here = arr[0]
    start = 0
    end = 0
    temp_start = 0
    
    for i in range(1, len(arr)):
        if arr[i] > max_ending_here + arr[i]:
            max_ending_here = arr[i]
            temp_start = i
        else:
            max_ending_here = max_ending_here + arr[i]
        
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = temp_start
            end = i
    
    return max_so_far, start, end
